import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Random;

public class HDS {
	private int[] elements;
	private int totalHeapSizes;
	private int heapSize;
	
	private int deadSpaceStart;
	
	private File inputFile;
	private File outputFile;

	private BufferedReader reader;
	private BufferedWriter writer;
	
	public HDS() {
		totalHeapSizes = 3;
		heapSize = 0;
		deadSpaceStart = 0;
		
		elements = new int[totalHeapSizes];
		
		inputFile = new File("inputNumbers.txt");
		outputFile = new File("outputNumbers.txt");
		
		//generateNumbers(10000, 10000);
		fillElementsArrayWithInitialHeapSize();
		writeNumbersToOutputFile();
	}
	
	private void fillElementsArrayWithInitialHeapSize() {
		try {
			String line = null;
			reader = new BufferedReader(new FileReader(inputFile));
			// Fill the elements array with the initial heapSize
			for (int i = 0; i < totalHeapSizes; i++) {
				if ((line = reader.readLine()) != null) {
					add(Integer.parseInt(line));
				}
			}

		} catch (FileNotFoundException e) {
			e.printStackTrace();
		} catch (NumberFormatException e) {
			e.printStackTrace();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
	
	private void writeNumbersToOutputFile() {
		int smallest = -1;
		String line = null;
		int totalRuns = 1;
		
		try {
			writer = new BufferedWriter(new FileWriter(outputFile));
			
			int heapSize1 = totalHeapSizes;
			int deadSpace = deadSpaceStart;
			
			while((line = reader.readLine()) != null) {
				smallest = getFirst();
				writer.write(smallest +"\n");
				
				int nextElement = Integer.parseInt(line);
				if(nextElement >= smallest) {
					add(nextElement);
				} else {
					deadSpace++;
					heapSize1--;
					
					elements[heapSize1] = nextElement;
				}
				
				if(heapSize1 == 0) {
					//break;
//					totalRuns++;
					writer.write("######################\n");
					buildHeap(deadSpace);
					deadSpace = 0;
					heapSize1 = totalHeapSizes;
					heapSize = heapSize1;
//					//buildHeap(deadSpace);
//					//heapSize = elementsOnHeap;
				}
			}
			
			System.out.println("DS: "+ deadSpace);
//			System.out.println("E: "+ heapSize);
			while(heapSize > 0) {
				writer.write(getFirst() +"\n");
			}
//			
//			System.out.println("E: "+ heapSize);
//			System.out.println("1: "+ elements[0]);
//			System.out.println("2: "+ elements[1]);
			
			writer.write("######################\n");
			//elementsOnHeap = 3;
			buildHeap(deadSpace);
			heapSize = deadSpace;
			while(heapSize > 0) {
				writer.write(getFirst() +"\n");
			}
			
			totalRuns++;
			
			System.out.println("Total runs: "+ totalRuns);
			writer.flush();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
	
	private void generateNumbers(int totalNumbers, int maxValue) {
		FileWriter writer = null;

		try {
			if(!inputFile.exists()) {
				writer = new FileWriter(inputFile);

				Random random = new Random();
				for (int i = totalNumbers - 1; i >= 0; i--) {
					writer.append((int) (random.nextInt(maxValue) + 1) + "\n");
				}
			}
		} catch (IOException e) {
			e.printStackTrace();
		} finally {
			if (writer != null) {
				try {
					writer.close();
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
		}
	}
	
	public int getFirst() {
		if(isEmpty()) {
			throw new RuntimeException("Heap is empty");
		}
		
		final int first = elements[0];
		elements[0] = elements[heapSize - 1];
		--heapSize;
		if(heapSize > 0) {
			percolateDown(0);
		}
		
		return first;
	}
	
	public void add(final int value) {
		if(heapSize == elements.length) {
			throw new RuntimeException("Heap is full");
		}
		
		elements[heapSize] = value;
		percolateUp(heapSize);
		heapSize++;
	}
	
	private void percolateUp(final int index) {
		if(index > 0) {
			final int parent = (index - 1) / 2;
			if(elements[parent] > elements[index]) {
				swap(parent, index);
				percolateUp(parent);
			}
		}
	}
	
	private void percolateDown(final int index) {
		final int leftChild = 2 * index + 1;
		final int rightChild = 2 * index + 2;
		
		if(rightChild < heapSize || leftChild < heapSize) {
			final int smallestChild = elements[rightChild] > elements[leftChild] ? leftChild : rightChild;
		
			if(elements[index] > elements[smallestChild]) {
				swap(smallestChild, index);
				percolateDown(smallestChild);
			}
		}
	}
	
	private void swap(int index1, int index2) {
		int tmp = elements[index1];
		elements[index1] = elements[index2];
		elements[index2] = tmp;
	}
	
	public boolean isEmpty() {
		return heapSize == 0;
	}
	
	public void buildHeap(int index) {
		for (int i = index / 2 - 1; i >= 0; i--) {
			percolateDown(i);
		}
	}
}